package 算法.字符串.排序.MSD基数排序;

import com.sun.accessibility.internal.resources.accessibility;

import sun.awt.image.OffScreenImage;
import util.LogUtils;
import edu.princeton.cs.algs4.Count;

/**
 * 【字符串排序：MSD自大而小 的基数排序】
 * 		
 *
 * @Date 2017-09-11 10：37
 * @author Administrator
 * @version
 */
public class MSD {
	int R = 256;
	int N;
	private void initData(String[] data) {
		data[0]   = "she";
		data[1]   = "sells";
		data[2]   = "seashells";
		data[3]   = "by";
		data[4]   = "the";
		data[5]   = "sea";
		data[6]   = "shore";
		data[7]   = "the";
		data[8]   = "shells";
		data[9]   = "she";
		data[10]  = "sells";
		data[11]  = "are";
		data[12]  = "surely";
		data[13]  = "seashells";
	}
	
	public void sort() {
		String[] data = new String[14];
		N = data.length;
		initData(data);
		sort(data, 0, N-1, 0);
	}
	
	private int charAt(String ele, int d) {
		if (d >= ele.length())	return -1;
		else return ele.charAt(d);
	}
	
	public void sort(String[] a, int lo, int hi, int d) {
		if (hi <= lo)	return;
		int[] count = new int[R+2];
		String[] aux = new String[a.length];
		for (int i = lo; i <= hi; i ++) {
			count[charAt(a[i], d)+1+1]++;
		}
		//转换为索引
		for (int r = 0; r < R+1; r ++) {
			count[r+1] += count[r];
		}
		//赋值
		for (int i = lo; i <= hi; i ++) {
			aux[count[charAt(a[i], d)+1]++] = a[i];
		}	
		//回写
		for (int i = lo; i <= hi; i ++) {
			a[i] = aux[i - lo];
		}
		//递归
		for (int r = 0; r < R; r ++) {
			sort(a, count[r]+lo, count[r+1]+lo-1, d+1);
		}
		//输出结果
		traverse(lo, hi, a);
	}

	
	private void traverse(int lo, int hi, String[] data) {
		for (int i = 0; i < data.length; i ++) {
			LogUtils.println("LSD>>"+lo+">>"+hi, data[i]);
		}
		LogUtils.println(">>>>>>>>>>>>>>>>", ">>>>>>>>>>>>>>>>>>>>>>>>>");
	}

	public static void main(String[] args) {
		new MSD().sort();
	}
}
